#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>

#include "imbus_internal.h"
#include "im_array.h"

#define MIN_ARRAY_SIZE  16

typedef struct _IMRealArray         IMRealArray;
typedef struct _IMRealPtrArray      IMRealPtrArray;

struct _IMRealArray
{
    IMChar      *array;
    IMSize       size;
    IMSize       alloc;
    IMSize       elt_size;
    IMSize       zero_terminated : 1;
    IMSize       clear : 1;
};

#define __im_array_elt_size(a,i) ((a)->elt_size * (i))
#define __im_array_elt_pos(a,i)  ((a)->array + __im_array_elt_size((a),(i)))
#define __im_array_elt_zero(a,pos,size)                     \
    (memset (__im_array_elt_pos ((a), pos), 0, __im_array_elt_size ((a), size)))
#define __im_array_zero_terminate(a)                        \
    do {                                                    \
        if ((a)->zero_terminated)                           \
            __im_array_elt_zero ((a), (a)->size, 1);        \
    } while (0)

struct _IMRealPtrArray
{
    IMPointer   *array;
    IMSize       size;
    IMSize       alloc;
};

/****************************** Internal functions **************************/
static IMSize
__nearest_pow (IMSize num)
{
    IMSize n = 1;

    while (n < num) n <<= 1;

    return n;
}

static void
__im_array_ensure_size (IMRealArray *array, IMSize add_size)
{
    IMPointer new_array;
    IMSize want_alloc =
        __im_array_elt_size (array, array->size + add_size + array->zero_terminated);

    if (want_alloc > array->alloc) {
        want_alloc = __nearest_pow (want_alloc);
        want_alloc = IM_MAX (want_alloc, MIN_ARRAY_SIZE);

        new_array = im_realloc (array->array, want_alloc);
        _im_assert (new_array != 0);

        array->array = new_array;
        array->alloc = want_alloc;
    }
}

static void
__im_ptr_array_ensure_size (IMRealPtrArray *array, IMSize add_size)
{
    if ((array->size + add_size) > array->alloc) {
        IMSize      new_alloc;
        IMPointer   new_array;
        new_alloc = __nearest_pow (array->size + add_size);
        new_alloc = IM_MAX(new_alloc, MIN_ARRAY_SIZE);
        new_array = im_realloc (array->array, sizeof (IMPointer) * new_alloc);

        _im_assert (new_array != 0);

        array->array = new_array;
        array->alloc = new_alloc;
    }
}

/****************************** Public functions **************************/
IMArray*
im_array_new (IMBool zero_terminated, IMBool clear, IMSize element_size)
{
    return im_array_new_reserved (zero_terminated, clear, element_size, 0);
}

IMArray*
im_array_new_reserved (IMBool zero_terminated, IMBool clear, IMSize element_size, IMSize reserved)
{
    IMRealArray *array = im_slice_new (IMRealArray);

    _im_assert (array != 0);

    array->array            = 0;
    array->size             = 0;
    array->alloc            = 0;
    array->zero_terminated  = (zero_terminated ? 1 : 0);
    array->clear            = (clear ? 1 : 0);
    array->elt_size         = element_size;

    if (array->zero_terminated || reserved) {
        __im_array_ensure_size (array, reserved);
        __im_array_zero_terminate (array);
    }

    return (IMArray*) array;
}

IMChar*
im_array_destroy (IMArray *array, IMBool free_memory)
{
    IMChar *mem;

    _im_return_val_if_fail (array, 0);

    if (free_memory) {
        im_free (array->array);
        mem = 0;
    } else {
        mem = array->array;
    }

    im_slice_delete(IMRealArray, (IMRealArray*)array);

    return mem;
}

IMArray*
im_array_append_vals (IMArray *array, IMConstPointer data, IMSize len)
{
    IMRealArray *ap = (IMRealArray*) array;

    _im_return_val_if_fail (ap, 0);
    _im_return_val_if_fail (data && len, 0);

    __im_array_ensure_size (ap, len);

    memcpy (__im_array_elt_pos (ap, ap->size), data, __im_array_elt_size (ap, len));

    ap->size += len;

    __im_array_zero_terminate (ap);

    return array;
}

IMArray*
im_array_prepend_vals (IMArray *array, IMConstPointer data, IMSize len)
{
    IMRealArray *ap = (IMRealArray*) array;

    _im_return_val_if_fail (ap, 0);
    _im_return_val_if_fail (data && len, 0);

    __im_array_ensure_size (ap, len);

    memmove (__im_array_elt_pos (ap, len), __im_array_elt_pos (ap, 0),
             __im_array_elt_size (ap, ap->size));

    memcpy (__im_array_elt_pos (ap, 0), data, __im_array_elt_size (ap, len));

    ap->size += len;

    __im_array_zero_terminate (ap);

    return array;
}

IMArray*
im_array_insert_vals (IMArray *array, IMSize index, IMConstPointer data, IMSize len)
{
    IMRealArray *ap = (IMRealArray*) array;

    _im_return_val_if_fail (ap, 0);
    _im_return_val_if_fail (data && len, 0);
    _im_return_val_if_fail (index <= ap->size, 0);

    __im_array_ensure_size (ap, len);

    if (index < ap->size)
        memmove (__im_array_elt_pos  (ap, len + index),
                 __im_array_elt_pos  (ap, index),
                 __im_array_elt_size (ap, ap->size - index));

    memcpy (__im_array_elt_pos (ap, index), data, __im_array_elt_size (ap, len));

    ap->size += len;

    __im_array_zero_terminate (ap);

    return array;
}

void
im_array_reserve (IMArray *array, IMSize size)
{
    IMRealArray *ap = (IMRealArray*) array;

    _im_return_if_fail (ap != 0);

    if (size > ap->size)
        __im_array_ensure_size (ap, (size - ap->size));
}

void
im_array_clear (IMArray *array)
{
    IMRealArray *ap = (IMRealArray*) array;

    _im_return_if_fail (ap != 0);

    ap->size = 0;

    __im_array_zero_terminate (ap);
}

void
im_array_set_size (IMArray *array, IMSize size)
{
    IMRealArray *ap = (IMRealArray*) array;

    _im_return_if_fail (ap != 0);

    if (size > ap->size) {
        __im_array_ensure_size (ap, (size - ap->size));

        if (ap->clear)
            __im_array_elt_zero (ap, ap->size, size - ap->size);
    }

    ap->size = size;

    __im_array_zero_terminate (ap);
}

IMArray*
im_array_remove_index (IMArray *array, IMSize index)
{
    IMRealArray *ap = (IMRealArray*) array;

    _im_return_val_if_fail (ap != 0, 0);
    _im_return_val_if_fail (index < ap->size, 0);

    if (index != ap->size - 1)
        memmove (__im_array_elt_pos (ap, index),
                 __im_array_elt_pos (ap, index + 1),
                 __im_array_elt_size (ap, ap->size - index - 1));

    -- ap->size;

    __im_array_zero_terminate (ap);

    return array;
}

IMArray*
im_array_remove_index_fast (IMArray *array, IMSize index)
{
    IMRealArray *ap = (IMRealArray*) array;

    _im_return_val_if_fail (ap != 0, 0);
    _im_return_val_if_fail (index < ap->size, 0);

    if (index != ap->size - 1)
        memcpy (__im_array_elt_pos (ap, index),
                __im_array_elt_pos (ap, ap->size - 1),
                __im_array_elt_size (ap, 1));

    -- ap->size;

    __im_array_zero_terminate (ap);

    return array;
}

IMArray*
im_array_remove_range (IMArray *array, IMSize index, IMSize length)
{
    IMRealArray *ap = (IMRealArray*) array;

    _im_return_val_if_fail (ap != 0, 0);
    _im_return_val_if_fail (index < ap->size, 0);
    _im_return_val_if_fail (index + length <= ap->size, 0);

    if (index + length != ap->size)
        memmove (__im_array_elt_pos (ap, index),
                 __im_array_elt_pos (ap, index + length),
                 __im_array_elt_size (ap, (ap->size - index - length)));

    ap->size -= length;

    __im_array_zero_terminate (ap);

    return array;
}

void
im_array_sort (const IMArray *array, IMCompareFunc compare_func)
{
    IMRealArray *ap = (IMRealArray*) array;

    _im_return_if_fail (ap != 0);
    _im_return_if_fail (compare_func != 0);

    if (ap->size && ap->array)
        qsort (ap->array, ap->size, ap->elt_size, compare_func);
}

void
im_array_sort_with_data (const IMArray *array, IMCompareDataFunc compare_func, IMPointer user_data)
{
    IMRealArray *ap = (IMRealArray*) array;

    _im_return_if_fail (ap != 0);
    _im_return_if_fail (compare_func != 0);

    if (ap->size && ap->array)
        im_qsort_with_data (ap->array, ap->size, ap->elt_size, compare_func, user_data);
}

IMSize
im_array_lower_bound (const IMArray *array, IMPointer val, IMCompareFunc compare_func)
{
    const IMRealArray *ap = (const IMRealArray*) array;
    IMChar *result = 0;

    _im_return_val_if_fail (ap != 0, 0);
    _im_return_val_if_fail (compare_func != 0, 0);

    /* There is no element, just return 0. */
    if (!ap->size || !ap->array) return 0;

    result = im_lower_bound (ap->array, ap->size, ap->elt_size, val, compare_func);
    return (result - ap->array) / ap->elt_size;
}

IMSize
im_array_lower_bound_with_data (const IMArray *array, IMPointer val, IMCompareDataFunc compare_func, IMPointer user_data)
{
    const IMRealArray *ap = (const IMRealArray*) array;
    IMChar *result = 0;

    _im_return_val_if_fail (ap != 0, 0);
    _im_return_val_if_fail (compare_func != 0, 0);

    /* There is no element, just return 0. */
    if (!ap->size || !ap->array) return 0;

    result = im_lower_bound_with_data (ap->array, ap->size, ap->elt_size, val, compare_func, user_data);
    return (result - ap->array) / ap->elt_size;
}

IMSize
im_array_upper_bound (const IMArray *array, IMPointer val, IMCompareFunc compare_func)
{
    const IMRealArray *ap = (const IMRealArray*) array;
    IMChar *result = 0;

    _im_return_val_if_fail (ap != 0, 0);
    _im_return_val_if_fail (compare_func != 0, 0);

    /* There is no element, just return 0. */
    if (!ap->size || !ap->array) return 0;

    result = im_upper_bound (ap->array, ap->size, ap->elt_size, val, compare_func);
    return (result - ap->array) / ap->elt_size;
}

IMSize
im_array_upper_bound_with_data (const IMArray *array, IMPointer val, IMCompareDataFunc compare_func, IMPointer user_data)
{
    const IMRealArray *ap = (const IMRealArray*) array;
    IMChar *result = 0;

    _im_return_val_if_fail (ap != 0, 0);
    _im_return_val_if_fail (compare_func != 0, 0);

    /* There is no element, just return 0. */
    if (!ap->size || !ap->array) return 0;

    result = im_upper_bound_with_data (ap->array, ap->size, ap->elt_size, val, compare_func, user_data);
    return (result - ap->array) / ap->elt_size;
}

void
im_array_foreach (const IMArray *array, IMFunc func, IMPointer user_data)
{
    const IMRealArray *ap = (const IMRealArray*) array;
    IMSize i;

    _im_return_if_fail (ap != 0);
    _im_return_if_fail (func != 0);

    for (i=0; i<ap->size; ++i)
        func (__im_array_elt_pos (ap, i), user_data);
}

void
im_array_foreach_in_range (const IMArray *array, IMSize index, IMSize length, IMFunc func, IMPointer user_data)
{
    const IMRealArray *ap = (const IMRealArray*) array;
    IMSize i;
    IMSize end;

    _im_return_if_fail (ap != 0);
    _im_return_if_fail (func != 0);

    end = IM_MIN (index + length, ap->size);

    for (i = index; i < end; ++i)
        func (__im_array_elt_pos (ap, i), user_data);
}

IMPtrArray*
im_ptr_array_new ()
{
    IMRealPtrArray *array = im_slice_new (IMRealPtrArray);

    _im_assert (array != 0);

    array->array = 0;
    array->size  = 0;
    array->alloc = 0;

    return (IMPtrArray *) array;
}

IMPtrArray*
im_ptr_array_new_reserved (IMSize reserved)
{
    IMPtrArray *array = im_ptr_array_new ();

    im_ptr_array_reserve (array, reserved);

    return array;
}
IMPointer*
im_ptr_array_destroy (IMPtrArray *array, IMBool free_memory)
{
    IMPointer* mem;

    _im_return_val_if_fail (array != 0, 0);

    if (free_memory) {
        im_free (array->array);
        mem = 0;
    } else {
        mem = array->array;
    }

    im_slice_delete(IMRealPtrArray, (IMRealPtrArray*)array);

    return mem;
}
void
im_ptr_array_clear (IMPtrArray *array)
{
    IMRealPtrArray *ap = (IMRealPtrArray*) array;

    _im_return_if_fail (ap != 0);

    ap->size = 0;
}
void
im_ptr_array_reserve (IMPtrArray *array, IMSize space)
{
    IMRealPtrArray *ap = (IMRealPtrArray*) array;

    _im_return_if_fail (ap != 0);

    if (space > ap->size)
        __im_ptr_array_ensure_size (ap, (space - ap->size));
}
void
im_ptr_array_set_size (IMPtrArray *array, IMSize size)
{
    IMRealPtrArray *ap = (IMRealPtrArray*) array;

    _im_return_if_fail (ap != 0);

    if (size > ap->size) {
        __im_ptr_array_ensure_size (ap, (size - ap->size));

        memset (ap->array + ap->size, 0, sizeof (IMPointer) * (size - ap->size));
    }

    ap->size = size;
}
void
im_ptr_array_free_unused_memory (IMPtrArray *array)
{
    IMRealPtrArray *ap = (IMRealPtrArray*) array;

    _im_return_if_fail (ap != 0);

    if (ap->array && ap->alloc > ap->size) {
        if (ap->size) {
            ap->array = im_realloc (ap->array, sizeof (IMPointer) * ap->size);
        } else {
            im_free (ap->array);
            ap->array = 0;
        }
        ap->alloc = ap->size;
    }
}
IMPtrArray*
im_ptr_array_prepend (IMPtrArray *array, IMPointer val)
{
    IMRealPtrArray *ap = (IMRealPtrArray*) array;

    _im_return_val_if_fail (ap != 0, 0);

    __im_ptr_array_ensure_size (ap, 1);

    memmove (ap->array + 1, ap->array, ap->size * sizeof (IMPointer));

    ap->array [0] = val;

    ++ ap->size;

    return array;
}
IMPtrArray*
im_ptr_array_append (IMPtrArray *array, IMPointer val)
{
    IMRealPtrArray *ap = (IMRealPtrArray*) array;

    _im_return_val_if_fail (ap != 0, 0);

    __im_ptr_array_ensure_size (ap, 1);

    ap->array [ap->size ++] = val;

    return array;
}
IMPtrArray*
im_ptr_array_insert (IMPtrArray *array, IMSize index, IMPointer val)
{
    IMRealPtrArray *ap = (IMRealPtrArray*) array;

    _im_return_val_if_fail (ap != 0, 0);
    _im_return_val_if_fail (index <= ap->size, 0);

    __im_ptr_array_ensure_size (ap, 1);

    if (index < ap->size)
        memmove (ap->array + index + 1, ap->array + index, (ap->size - index) * sizeof (IMPointer));

    ap->array [index] = val;
    ++ ap->size;

    return array;
}
IMPointer
im_ptr_array_remove (IMPtrArray *array, IMSize index)
{
    IMRealPtrArray *ap = (IMRealPtrArray*) array;
    IMPointer result;

    _im_return_val_if_fail (ap != 0, 0);
    _im_return_val_if_fail (index < ap->size, 0);

    result = ap->array [index];

    if (index < ap->size - 1)
        memmove (ap->array + index, ap->array + index + 1, (ap->size - index - 1) * sizeof (IMPointer));

    -- ap->size;

    return result;
}
IMPointer
im_ptr_array_remove_fast (IMPtrArray *array, IMSize index)
{
    IMRealPtrArray *ap = (IMRealPtrArray*) array;
    IMPointer result;

    _im_return_val_if_fail (ap != 0, 0);
    _im_return_val_if_fail (index < ap->size, 0);

    result = ap->array [index];

    if (index < ap->size - 1)
        ap->array [index] = ap->array [ap->size - 1];

    -- ap->size;

    return result;
}
void
im_ptr_array_remove_range (IMPtrArray *array, IMSize index, IMSize length)
{
    IMRealPtrArray *ap = (IMRealPtrArray*) array;

    _im_return_if_fail (ap != 0);
    _im_return_if_fail (index < ap->size);
    _im_return_if_fail (index + length <= ap->size);

    if (index + length < ap->size)
        memmove (& (ap->array [index]), & (ap->array [index + length]),
                 sizeof (IMPointer) * (ap->size - (index + length)));

    ap->size -= length;
}

typedef struct
{
    IMCompareDataFunc compare;
    IMPointer     user_data;
} __IMCompareDataFuncUserDataPair;

static int
__ptr_array_compare (IMConstPointer v1, IMConstPointer v2, IMPointer u)
{
    return  ((IMCompareFunc)u) (*((IMConstPointer*)v1), *((IMConstPointer*)v2));
}

static int
__ptr_array_compare_with_data (IMConstPointer v1, IMConstPointer v2, IMPointer u)
{
    return  ((__IMCompareDataFuncUserDataPair*)u)->compare (
                *((IMConstPointer*)v1), *((IMConstPointer*)v2),
                ((__IMCompareDataFuncUserDataPair*)u)->user_data);
}

void
im_ptr_array_sort (IMPtrArray *array, IMCompareFunc compare_func)
{
    IMRealPtrArray *ap = (IMRealPtrArray*) array;

    _im_return_if_fail (ap != 0);
    _im_return_if_fail (compare_func != 0);

    if (ap->size && ap->array)
        im_qsort_with_data (ap->array, ap->size, sizeof (IMPointer),
                            __ptr_array_compare, compare_func);
}
void
im_ptr_array_sort_with_data (IMPtrArray *array, IMCompareDataFunc compare_func, IMPointer user_data)
{
    __IMCompareDataFuncUserDataPair d;
    IMRealPtrArray *ap = (IMRealPtrArray*) array;

    _im_return_if_fail (ap != 0);
    _im_return_if_fail (compare_func != 0);

    d.compare   = compare_func;
    d.user_data = user_data;

    if (ap->size && ap->array)
        im_qsort_with_data (ap->array, ap->size, sizeof (IMPointer),
                            __ptr_array_compare_with_data, &d);
}
IMSize
im_ptr_array_lower_bound (const IMPtrArray *array, IMPointer val, IMCompareFunc compare_func)
{
    const IMRealPtrArray *ap = (const IMRealPtrArray*) array;
    IMPointer *result = 0;

    _im_return_val_if_fail (ap != 0, 0);
    _im_return_val_if_fail (compare_func != 0, 0);

    /* There is no element, just return 0. */
    if (!ap->size || !ap->array) return 0;

    result = im_lower_bound_with_data (ap->array, ap->size,
                                       sizeof (IMPointer), &val,
                                       __ptr_array_compare, compare_func);
    return result - ap->array;
}
IMSize
im_ptr_array_upper_bound (const IMPtrArray *array, IMPointer val, IMCompareFunc compare_func)
{
    const IMRealPtrArray *ap = (const IMRealPtrArray*) array;
    IMPointer *result = 0;

    _im_return_val_if_fail (ap != 0, 0);
    _im_return_val_if_fail (compare_func != 0, 0);

    /* There is no element, just return 0. */
    if (!ap->size || !ap->array) return 0;

    result = im_upper_bound_with_data (ap->array, ap->size,
                                       sizeof (IMPointer), &val,
                                       __ptr_array_compare, compare_func);
    return result - ap->array;
}
IMSize
im_ptr_array_lower_bound_with_data (const IMPtrArray *array, IMPointer val, IMCompareDataFunc compare_func, IMPointer user_data)
{
    __IMCompareDataFuncUserDataPair d;
    const IMRealPtrArray *ap = (const IMRealPtrArray*) array;
    IMPointer *result = 0;

    _im_return_val_if_fail (ap != 0, 0);
    _im_return_val_if_fail (compare_func != 0, 0);

    /* There is no element, just return 0. */
    if (!ap->size || !ap->array) return 0;

    d.compare   = compare_func;
    d.user_data = user_data;

    result = im_lower_bound_with_data (ap->array, ap->size,
                                       sizeof (IMPointer), &val,
                                       __ptr_array_compare_with_data, &d);
    return result - ap->array;
}
IMSize
im_ptr_array_upper_bound_with_data (const IMPtrArray *array, IMPointer val, IMCompareDataFunc compare_func, IMPointer user_data)
{
    __IMCompareDataFuncUserDataPair d;
    const IMRealPtrArray *ap = (const IMRealPtrArray*) array;
    IMPointer *result = 0;

    _im_return_val_if_fail (ap != 0, 0);
    _im_return_val_if_fail (compare_func != 0, 0);

    /* There is no element, just return 0. */
    if (!ap->size || !ap->array) return 0;

    d.compare   = compare_func;
    d.user_data = user_data;

    result = im_upper_bound_with_data (ap->array, ap->size,
                                       sizeof (IMPointer), &val,
                                       __ptr_array_compare_with_data, &d);
    return result - ap->array;
}
void
im_ptr_array_foreach (const IMPtrArray *array, IMFunc func, IMPointer user_data)
{
    const IMRealPtrArray *ap = (const IMRealPtrArray*) array;
    IMSize i;

    _im_return_if_fail (ap != 0);
    _im_return_if_fail (func != 0);

    for (i=0; i<ap->size; ++i)
        func (ap->array [i], user_data);
}
void
im_ptr_array_foreach_in_range (const IMPtrArray *array, IMSize index, IMSize length, IMFunc func, IMPointer user_data)
{
    const IMRealPtrArray *ap = (const IMRealPtrArray*) array;
    IMSize i;
    IMSize end;

    _im_return_if_fail (ap != 0);
    _im_return_if_fail (func != 0);

    end = IM_MIN (index + length, ap->size);

    for (i = index; i < end; ++i)
        func (ap->array [i], user_data);
}

/*
vi:ts=4:nowrap:ai:expandtab
*/
